package leetcode;


import java.util.Arrays;

/**
 *
 * 动态规划
 */
public class DongGui {

    /**
     *
     * @param coins 可以兑换的面值数组，这里是【1，2，5，10，20，50，100】
     * @param K 兑换目标金额K
     * @return 返回最小值，当K==0时返回0
     */
    public static int CoinChange(int[] coins, int K) {

        //动态规划数组用来存储从0到K的所有最优解，无论K为多少，最优解都是dp[k];
        //dp[k]的取值取决于dp[0]到dp[k-1]的值，因此动态规划的关键在于求dp数组从0到K索引的值
        int[] dp =new int[K+1];
        //fill函数用来将dp数组的所有索引值都填充为K+1，比如K=11，dp[k]是11+1，这样设置兑换数目最差的情况
        Arrays.fill(dp,K+1);
        //dp[0]一定是0，k等于0时，没有最优解所以是0
        dp[0]=0;
        //从这一步开始遍历dp数组，从1到K逐步计算dp[i]的最优解；
        for (int i=1;i<=K;i++){
            //第二个for循环用来遍历所有面值的金额来决策出每一步选择哪个面值的金额
            for (int j=0;j<coins.length;j++){
                if (coins[j]<=i) {
                    //比如K=11，有以下三种兑换方法dp[11-1]+1;dp[11-2]+1;dp[11-5]+1
                    // 关键在于比较得出三者最小值作为dp[i]中，这里用Min函数比较得出最小值
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        //所有从0到K的最优解已求出，如果dp[K]不小于K+1说明没有最优解，返回-1，否则返回最优解dp【K】
        return dp[K] < K+1 ? dp[K] : -1;
    }

    public static void main(String[] args) {
        int[] coins = new int[]{1,2,5,10,20,50,100};
        int res = CoinChange(coins,11);
        System.out.println(res);
    }
}
